HW#1 --- last modified February 07 2019 23:07:54..

Solution set.

Due date: Feb 15

Files to be submitted:
  Hw1.zip

Purpose:To learn about search strategies for problem solving agents

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- By code or by hand find solution nodes in a state space using the A* algorithm.

Specification:

A tile game is game played on an n x m rectangle of squares. Each square can be either empty, have a movable tile in it, or have an non-movable tile in it. A valid starting configuration for a tile game has j movable tiles with labels 1, ..., j, and k non-movable tiles such that 1 ≤ j + k < n × m. You can assume `j` is a single digit number. A move in a tile game consists in swapping a movable tile with an empty tile which is either immediately above or below it or to its immediate left or right. We say a square (x,y) is less than a square (x', y') if x < x' or x = x' and y < y'. The goal configuration of a tile game is the configuration in which the tile labeled j is on a square less than any empty square and in which if w < v ≤ j are tile labels then the tile labeled w is on a square less than the tile labeled v. The 8-puzzle is a specific case of a tile puzzle. The goal of this assignment is to make a Python script which solves tile games (if they are solvable) using the A* algorithm. For CS286 Sec 2 students the description of what you need to do in addition to this base assignment can be found after the details about what I want for your tile game.

I want people in this class to use a common development environment to facilitate me problem solving question. To this end, please download gedit which is available for all major OS's. Set up your environment in gedit so that it draws all white-space characters and displays a line at the 80 character position. Also, set it up so that when you hit tab it draws four spaces. Your submission should not have any tab characters in it and each line should be less than 80 characters. Your Python code should follow the Pep 8 coding guidelines.

Your program will be run from the command line as follows:

python tile_game.py file_name

Here file_name is the name of a text file that I supply containing the initial configuration of the tile_game. This file uses '.' to represent an empty tile, '#" to represent a non-movable tile, and the numbers 1 to j for the tiles. As an example, the file might contain the following:

2..1
3.#4

After read this input, your program should try to solve the tile puzzle using the A* algorithm, and print out a sequences of boards, each representing one move in the steps needed to solve the puzzle. After this your program should stop. If there is no solution, your program should output "No solution" on a new line and stop. the sequences of moves. The exact sequence of steps will depend on the heuristic you use in your A* algorithm. One possible output, for the above puzzle would be:

2..1
3.#4

2..1
.3#4

...1
23#4

..1.
23#4

.1..
23#4

1...
23#4

13..
2.#4

13..
.2#4

1.3.
.2#4

123.
..#4

1234
..#.

Put your script tile_game.py in your ZIP submission file. Also, put a readme.txt file with any additional notes which could help me grade your project.

CS286 Sec 2 students should in addition to the above read the paper: Adaptive On-Line Page Importance Computation by Abiteboul, Preda, and Cobena. You should then write a two page essay describing the web crawling algorithms covered in the paper and answering the following questions: Can the web crawling task be framed as a problem or as a sequence of problems that might be solved by a problem solving agent? If you had the job of finding the 1000 most important web sites on the web, could you solve this problem with A*? What kind of heuristics could you use? How could you tell when you had reached your goal? Would you only need to download a 1000 web sites? If not, come up with reasonable stopping criteria to make this like A*.

Point Breakdown